package com.hyb.algorithm.data.struct.dp;

/**
 * @Author: huyanbing
 * @Date: 2021/8/27 4:26 下午
 * <p>
 * 651
 * https://blog.csdn.net/weixin_30764771/article/details/97515063
 */
public class MaxA {

    public static void main(String[] args) {
        MaxA exe = new MaxA();
        int ret = exe.maxA(20);

        System.out.println(ret);
    }


    /**
     * dp[i] 表示 操作i次以后 最多显示多少个A
     *
     * @param n
     * @return
     */
    public int maxA(int n) {

        int[] dp = new int[n+1];

        dp[0] = 0;


        for (int i = 1; i <=n; i++) {
            //j 是第几个键 按ctrl+a ctrl+c
            for (int j = 2; j < i; j++) {
                //dp[i - 1] + 1  继续按 A     按 ctrl+a ctrl+c ctrl+v  dp[j - 2] * (i - j + 1)
                dp[i] = Math.max(dp[i - 1] + 1, dp[j - 2] * (i - j + 1));
            }
        }

        // N 次按键 最多显示几个A
        return dp[n];

    }

}
